package com.sh.二叉树;

import java.util.*;

/**
 * @Auther: sh
 * @Version 1.0
 * @Description:
 */
public class Test {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        if (root == null) {
            return res;
        }
        Stack<TreeNode> stack = new Stack<>();
        TreeNode temp = root;
        while (stack.isEmpty() == false || temp != null) {
            if (temp != null) {
                stack.push(temp);
                temp = temp.left;
            } else {
                temp = stack.pop();
                res.add(temp.val);
                temp = temp.right;
            }
        }
        return res;

    }

    private void funInorderTraversal(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        funInorderTraversal(root.left, res);
        res.add(root.val);
        funInorderTraversal(root.right, res);
    }


    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDepth(root.left);
        int right = maxDepth(root.right);
        int res = Math.max(left, right) + 1;
        return res;

    }


    public TreeNode invertTree(TreeNode root) {
        if (root == null) {
            return root;
        }
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        invertTree(root.left);
        invertTree(root.right);
        return root;
    }

    public boolean isSymmetric(TreeNode root) {
        if (root == null) {
            return true;
        }
        boolean res = funIsSymmetric(root.left, root.right);
        return res;

    }

    private boolean funIsSymmetric(TreeNode left, TreeNode right) {
        if (left == null && right == null) return true;
        if (left != null && right == null) return false;
        if (left == null && right != null) return false;
        if (left.val != right.val) return false;
        boolean b = funIsSymmetric(left.left, right.right);
        boolean b1 = funIsSymmetric(left.right, right.left);
        return b && b1;
    }

    public static int[] twoSum(int[] nums, int target) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int temp = nums[i];    // 循环到这个数
            if (map.containsKey(target - temp)) {
                return new int[]{i, map.get(target - temp)};
            }
            map.put(temp, i);
        }
        return null;
    }

    public static void main(String[] args) {
        int nums[] = {2, 7, 11, 15};
        twoSum(nums, 9);

    }
}

